package bfs;

import java.util.LinkedList;
import java.util.Queue;

public class 零一矩阵 {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        Queue<int[]> queue = new LinkedList<>();
        int[][] res = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j]==0)
                    queue.add(new int[]{i,j});
                else
                    res[i][j] = -1;
            }
        }
        while (!queue.isEmpty()){
            int[] poll = queue.poll();
            int x = poll[0];
            int y = poll[1];
            for (int i = 0; i < 4; i++) {
                int x1 = x + dirs[i][0];
                int y1 = y + dirs[i][1];
                if (x1>=0 && x1<m && y1>=0 && y1<n && res[x1][y1]==-1){
                    //每个-1的最短距离都是由邻居的最短距离得来的，即邻居最短距离+1
                    res[x1][y1] = res[x][y]+1;
                    queue.offer(new int[]{x1,y1});
                }
            }
        }
        return res;
    }
}
